package org.ala.everyday;

/**
 * 给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
 *
 * 每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
 *
 * 给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：time = [1,2,3], totalTrips = 5
 * 输出：3
 * 解释：
 * - 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
 *   已完成的总旅途数为 1 + 0 + 0 = 1 。
 * - 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
 *   已完成的总旅途数为 2 + 1 + 0 = 3 。
 * - 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
 *   已完成的总旅途数为 3 + 1 + 1 = 5 。
 * 所以总共完成至少 5 趟旅途的最少时间为 3 。
 * 示例 2：
 *
 * 输入：time = [2], totalTrips = 1
 * 输出：2
 * 解释：
 * 只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
 * 所以完成 1 趟旅途的最少时间为 2 。
 *
 *
 * 提示：
 *
 * 1 <= time.length <= 105
 * 1 <= time[i], totalTrips <= 107
 *
 * @author ala
 * @date 2024-10-05 01:13
 */
public class Q2187 {

    public static void main(String[] args) {
        Q2187 q = new Q2187();

//        int[] time = {1,2,3};
//        int totalTrips = 5;

//        int[] time = {2};
//        int totalTrips = 1;

        int[] time = {5,10,10};
        int totalTrips = 9;

//        int[] time = {9,2};
//        int totalTrips = 8;

//        int[] time = {1};
//        int totalTrips = 1;

        System.out.println(q.minimumTime(time, totalTrips));
    }

    public long minimumTime(int[] time, int totalTrips) {
        return V1(time, totalTrips);
    }
    /**
     *  1）时间下界是min(time)，上界是c * max(time)
     *  2）c 从1开始探测上界
     *      c * max(time) > totalTrips，使不等式成立的最小 c * max(time)
     *  3）在上下界之间二分
     */
    protected long V1(int[] time, int totalTrips) {
        long mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
        for (int t : time) {
            mx = Math.max(mx, t);
            mn = Math.min(mn, t);
        }
        long l = 1, r = maxTimes(mx, time, totalTrips);
        if (r == 1) {return 1;}

        while (l < r) {
            long m = l + ((r - l) >> 1);
            int t = check(m, time, totalTrips, false);

            if (t == 0) {return m;}
            if (l == m) {
                if (t > 0) {return l;}
                else {return r;}
            }

            if (t < 0) {
                l = m;
            } else {
                r = m;
            }
        }
        return -1;
    }

    /**
     *  探测二分上界。如果顺便发现了 == 0 的情况，说明正好找到了答案
     */
    protected long maxTimes(long mx, int[] time, long totalTrips) {
        int t = check(mx, time, totalTrips, true);
        if (t == 0) {
            return -mx;
        }
        while (t < 0) {
            mx <<= 1;
            t = check(mx, time, totalTrips, true);
            if (t == 0) {
                return -mx;
            }
        }
        return mx;
    }
    protected int check(long tag, int[] time, long totalTrips, boolean allow0) {
        int sum = 0;
        for (int t : time) {
            sum += (int)(tag / t);
        }
        //  奇偶的原因，有个用例答案是24，但25这里也等于0
        if (allow0 && sum == totalTrips) {return 0;}
        return sum < totalTrips ? -1 : 1;
    }
}
